# 需要画二维表理解此算法
# str1的每个字符对应表行头部 str2的每个字符对应表列头部 边界条件为其中一个是空字符串的情况
# 对应的二维表count如下：
#     '' s  d  w  e
#  '' 0  1  2  3  4
#  d  1  1  1  2  3
#  s  2  1  2  2  3
#  a  3  2  2  3  3
#  a  4  3  3  3  4
#  s  5  4  4  4  4
# 创建出一个二维表count，二维表的首行和首列都是确定的，从而能够进行后续的递推计算。--边界条件
# 二维表除了首行和首列，其它行列需要不断扩展，直到把整个二维表填充满，最后一个值即为解。--状态转换
# count[i+1][j+1]的值：如果行列的字母相同，则该值为对角线数字；如果行列字母不等，则该值为对角线、左邻、上邻中的最小数加1

# # # # # # 下面为算法实现过程 # # # # # #
# 待计算的字符串
str1 = 'sdwe'
str2 = 'dsaas'

# 创建二维表
count = []
len_1 = len(str1)
len_2 = len(str2)
for i in range(len_2 + 1):
    inner =[]
    for j in range(i, i + len_1 + 1):
        inner.append(j)
    count.append(inner)
print(count)

# 不断扩充二维表的值
for i in range(len(str2)):
    for j in range(len(str1)):
        if str1[j] != str2[i]:
            count[i+1][j+1] = min(count[i][j], count[i+1][j], count[i][j+1]) + 1
        elif str1[j] == str2[i]:
            count[i + 1][j + 1] = count[i][j]

# 二维表中最后一个值即为解
r = count[len_2][len_1]
print(r)
